package likou;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/07/15 14:25
 */
public class _105 {
    public static void main(String[] args) {
        System.out.println(buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7}));
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if (len == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int i = 0;
        for (; i < len; i++) {
            if (inorder[i] == preorder[0]) {
                break;
            }
        }
        //分割，i前为左树，i后为右树
        //左树继续
        if (i != 0) {
            if (i != 1) {
                int[] preLeft = new int[i];//[1,i]
                int[] inLeft = new int[i];//[0,i-1]
                System.arraycopy(preorder, 1, preLeft, 0, i);
                System.arraycopy(inorder, 0, inLeft, 0, i);
                root.left = buildTree(preLeft, inLeft);
            } else {
                root.left = new TreeNode(preorder[1]);
            }
        }
        //右树继续
        if (i != len - 1) {
            if (i != len - 2) {
                int[] preRight = new int[len - i - 1];//[i+1,len]
                int[] inRight = new int[len - i - 1];//[i+1,len]
                System.arraycopy(preorder, i + 1, preRight, 0, len - i - 1);
                System.arraycopy(inorder, i + 1, inRight, 0, len - i - 1);
                root.right = buildTree(preRight, inRight);
            } else {
                root.right = new TreeNode(preorder[i + 1]);
            }
        }
        return root;
    }
}
